package offerbook;


import baseclass.e_tree.Code02_AfterNode_后继节点;
import baseclass.e_tree.Code03_PreNode_前驱节点;

/**
 *
 * 在二叉树的中序遍历中，寻找节点的前驱和后继。
 *
 * 具体分析见{@link Code02_AfterNode_后继节点}
 * 具体分析见{@link Code03_PreNode_前驱节点}
 */


public class Code58_GetBSTNext_后继节点 {
    /**
     * 中序遍历的后继节点。
     * 如果当前节点有右孩子，那么其右孩子的最左孩子是当前节点的后继节点；
     * 如果当前节点无右孩子，那么一直向上找，直到当前节点是其父节点的左孩子。
     *
     * 中序遍历中，最后遍历的那个节点没有后继。注意此时最后的父节点是null。
     */
    public TreeLinkNode getNext(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }
        if(pNode.right != null){
            pNode = pNode.right;
            while (pNode.left != null){
                pNode = pNode.left;
            }
            //pNode.left ==null
            return pNode;
        }

        TreeLinkNode parent = pNode.next;
        //next是指向父节点的指针
        //当parent是null则代表此时的pNode是根节点
        while (parent != null && pNode != parent.left){
            pNode = parent;
            parent = pNode.next;
        }
        return parent;
    }

    /**
     * 寻找中序遍历中的前驱节点
     * 1.如果当前节点有左孩子，那么其左孩子的最右孩子就是
     * 2.如果当前节点没有左孩子，那么一直往上找，直到当前节点是其父节点的右孩子
     */
    public TreeLinkNode getPre(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }
        if(pNode.left != null){
            pNode = pNode.left;
            while (pNode.right != null){
                pNode = pNode.right;
            }
            return pNode;
        }
        //case2
        TreeLinkNode parent = pNode.next;
        while (parent != null && pNode != parent.right){
            pNode = parent;
            parent = pNode.next;
        }
        return parent;
    }

}
